#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

void radixSort(int *arr, int len)
{
    int max = arr[0];
    for(int i{1}; i < len; i++){
        if(max < abs(arr[i])){
            max = abs(arr[i]);
        }
    }

    int d = std::to_string(max).size();

    vector<vector<int>> bucket(20);

    for(int i{}, mod{10}, dev{1}; i < d; i++, mod *= 10, dev *= 10){
        for(int j{}; j < len; j++){
            int idx = (arr[j] % mod) / dev + 10;
            bucket[idx].push_back(arr[j]);
        }
    
        int idx = 0;
        for(vector<int> &vec: bucket){
            for(int num: vec){
                arr[idx++] = num;
            }
            vec.clear();
        }
    }


    for(int i{}; i < len; i++){
        cout << arr[i] << " ";
    }
    cout << endl;

}

int main(int args, char *argv[])
{
    int arr[] = {0, 1, 3, -3, 1, 24, 1, 32, -523};
    int len = sizeof(arr) / sizeof(int);
    radixSort(arr, len); 

    return 0;
}